package com.cjlgb.design.common.core.util;

import java.util.*;

/**
 * @author WFT
 * @date 2019/8/14
 * description: 树形工具类
 */
public class TreeUtil {

    public static <Entity extends Tree<Entity>> List<Entity> build(List<Entity> entityList){
        if (entityList.size() == 0){
            return entityList;
        }
        /*
            排序后得到：
             [
                { id : 1, pid : 0, sort : 1 },
                { id : 2, pid : 1, sort : 1 },
                { id : 3, pid : 0, sort : 2 },
                { id : 4, pid : 3, sort : 1 }
            ]
         */
        entityList.sort(Comparator.comparing(Entity :: getSort));
        /*
            分组后：
             {
                0 : [
                    { id : 1, pid : 0, sort : 1 },
                    { id : 3, pid : 0, sort : 2 }
                ],
                1 : [ { id : 2, pid : 1, sort : 1 } ],
                3 : [ { id : 4, pid : 3, sort : 1 } ],
            }
         */
        Map<Long, List<Entity>> groupMap = new HashMap<>(16);
        entityList.forEach(entity -> {
            List<Entity> list = groupMap.get(entity.getPid());
            if (null == list){
                list = new ArrayList<>();
                list.add(entity);
                groupMap.put(entity.getPid(),list);
            }else {
                list.add(entity);
            }
        });
        //  得到Pid列表
        List<Long> pidList = new ArrayList<>(groupMap.keySet());
        pidList.sort(Comparator.comparing(Long::longValue));

        for (int i = pidList.size() - 1; i > 0; i--){
            //  数值最大的Pid
            long thisKey = pidList.get(i);
            //  寻找父节点
            for (int j = i - 1; j >= 0; j--){
                List<Entity> list = groupMap.get(pidList.get(j));
                //  递归寻找父节点
                if (recursion(list,thisKey,groupMap)){
                    break;
                }
            }
        }
        return groupMap.get(pidList.get(0));
    }

    private static <Entity extends Tree<Entity>> boolean recursion(List<Entity> list,long thisKey,Map<Long, List<Entity>> groupMap){
        for (Entity entity : list){
            if (entity.getId().equals(thisKey)){
                List<Entity> children = groupMap.get(thisKey);
                entity.setChildren(children);
                groupMap.remove(thisKey);
                return true;
            }else if (null != entity.getChildren()){
                return recursion(entity.getChildren(),thisKey,groupMap);
            }
        }
        return false;
    }


    public interface Tree<Entity> {

        /**
         * 唯一标识
         * @return long
         */
        Long getId();

        /**
         * 父级唯一标识
         * @return long
         */
        Long getPid();

        /**
         * 排序值
         * @return int
         */
        Integer getSort();

        /**
         * 设置子节点列表
         * @param children 子节点列表
         */
        void setChildren(List<Entity> children);

        /**
         * 获取子节点列表
         * @return List<Entity>
         */
        List<Entity> getChildren();
    }


}
